//冒泡排序
/*
    从后往前(或从前往后)两两比较相邻元素的值，若为逆序，则交换他们，直到序列比较完。称这样的过程为"一趟"冒泡排序。
最多只需n-1趟排序，每一趟排序确定一个元素的最终位置(在有序序列里的位置),已经确定最终位置的元素在之后的处理中无需再对比。
如果某一趟排序中未发生"交换"操作，则证明当前序列已经有序，算法可提前结束。
*/
/*
    稳定
    平均时间复杂度O(n^2)，最好时间复杂度O(n)，最坏时间复杂度O(n^2);
    空间复杂度O(1);
*/

#include <iostream>

using namespace std;

void swap(int &a, int &b) //交换a和b的值
{
    int temp = a;
    a = b;
    b = temp;
    return;
}

void BubbleSort(int A[], int n) //冒泡排序(默认升序)【这里是从后往前冒泡，也可以从前往后冒泡】
{
    for (int i = 0; i < n - 1; ++i) //n-1趟排序
    {
        bool flag = false;  //表示当前这一趟排序是否出现交换操作
        for (int j = n - 1; j > i; --j) //一趟冒泡过程(在未排序的序列中选一个最小的值冒泡到已排序序列最后面)
            if (A[j-1] > A[j])  //选出A[j-1]和A[j]中小的那一个放在A[j-1]的位置，以便下一轮比较交换
            {
                swap(A[j - 1], A[j]); //交换操作
                flag = true;          //这一趟排序出现交换操作
            }
        if(flag == false) //如果这一趟排序没有发生交换，则证明此时该序列已经有序，退出排序
            return;
    }
}

int main()
{
    int A[100] = {2, 4, 3, 7, 9, 1, 6, 5, 8};
    BubbleSort(A, 9);
    for (int i = 0; i < 9; ++i)
        cout << A[i] << ' ';
    return 0;
}